Many computer-based applications used for, for example, creating Boolean satisfiability filters, signal and image processing, materials science and fluid dynamics simulations, and computational finance require solving linear systems of equations. One approach to solving these linear systems of equations is to implement Gaussian elimination. Gaussian elimination, also known as row reduction, involves a sequence of operations performed on a corresponding matrix of coefficients. Row operations, such as swapping two rows, multiplying a row by a non-zero number, and adding a multiple of one row to another row, are performed on the corresponding matrix of coefficients until the matrix is in row echelon form. Accordingly, to solve a system of n equations for n unknowns, requires n(n+1)/2 divisions, (2n3+3n2−5n)/6 multiplications, and (2n3+3n2−5n)/6 subtractions for a total of approximately 2n3/3 operations with an arithmetic complexity of O(n3). While highly reliable, the arithmetic complexity of O(n3) is cost prohibitive for systems with millions of equations as in such applications, for example, as modern network security and large scale physical simulations.
The description provided in the background section should not be assumed to be prior art merely because it is mentioned in or associated with the background section. The background section may include information that describes one or more aspects of the subject technology.